// Return the number of nodes in a list
//
void MoveNode(item* *destRef,item* *sourceRef)
{
	item* newNode = *sourceRef; // the front source node
	(newNode != NULL);
	*sourceRef = newNode->next; // Advance the source pointer
	newNode->next = *destRef; // Link the old dest off the new node
	*destRef = newNode; // Move dest to point to the new node

}
//
//
//
item* SortedMerge(item* a,item* b) 
{
	item dummy;			// a dummy first node to hang the result on
	item* tail;
	tail = &dummy;// Points to the last result node --
								// so tail->next is the place to add
								// new nodes to the result.
	dummy.next = NULL;
	while (1) 
	{
		if (a == NULL) { // if either list runs out, use the other list
		tail->next = b;
		break;
		}
		else if (b == NULL) {
		tail->next = a;
		break;
		}
		
		if (a->val <= b->val) {
		MoveNode(&(tail->next), &a);
		}
		else {
		MoveNode(&(tail->next), &b);
		}
		tail = tail->next;
	}
	return(dummy.next);
}

// Split head into 'a' and 'b' sublists
void FrontBackSplit(item* source,item* *frontRef,item* *backRef) {
	int len = Length(source);
	int i;
	item* current = source;

	if (len < 2) {
		*frontRef = source;
		*backRef = NULL;
	}
	else 
	{
		int hopCount = (len-1)/2; //(figured these with a few drawings)
		for (i = 0; i<hopCount; i++) 
		{
			current = current->next;
		}
	// Now cut at current
	*frontRef = source;
	*backRef = current->next;
	current->next = NULL;
	}
}


void MergeSort(item* *headRef) {
	item* argHead;
	argHead = *headRef;
	item* a;
	item* b;
	// Check if number of elements to sort is one or less 
	if ((argHead == NULL) || (argHead->next == NULL)) {
	return;
	}
	
	// Split head into 'a' and 'b' sublists
	FrontBackSplit(argHead, &a, &b); 
	//
	MergeSort(&a); // Recursively sort the sublists
	MergeSort(&b);

	*headRef = SortedMerge(a, b); // answer = merge the two sorted lists together
}